Ngày 9 tháng 2 năm 1963, Nguyễn Văn Trỗi lần đầu gặp gỡ chị Phan Thị Quyên (sinh năm 1944), qua sự mai mối của chị họ cùng làm công nhân tại hãng bông Bạch Tuyết. Quê nội chị Quyên ở thôn Văn Giáp (xã Bạch Đằng, huyện Thường Tín, Hà Đông cũ, nay thuộc Hà Nội). Từ năm 1917, dân Văn Giáp đã phiêu bạt tứ xứ, nhiều người vào Nam Bộ kiếm sống. Năm 1937, bố mẹ chị Quyên cũng vào Nam. Lúc đầu họ tá túc ở đồn điền Chúp thuộc tỉnh Kampong Cham, Campuchia; cụ ông làm nghề cắt tóc, cụ bà bán hàng xén. Vì tham gia hoạt động yêu nước nên cụ ông bị lùng bắt, phải trốn về Sài Gòn vào năm 1956. Về Sài Gòn, gia đình chị Quyên sống ở 104 Lê Quốc Hưng (nay thuộc phường 12, quận 4, Thành phố Hồ Chí Minh).[6]

Ngày 21 tháng 4 năm 1964 (ngày 10 tháng 3 âm lịch), hai người làm đám cưới. Sau ngày cưới, vợ chồng anh cùng người cháu tên Hứa về ở chung nhà với một gia đình đồng hương tại số 1701, ấp Tây Ba, gần xứ đạo Bùi Chu - Phát Diệm.

Chỉ 19 ngày sau lễ kết hôn thì Nguyễn Văn Trỗi bị bắt. Vợ anh cũng bị giam giữ vài ngày sau đó nhưng được thả ra vì không có bằng chứng kết tội. Hai người chưa có con với nhau.[7] Sau đó Phan Thị Quyên tham gia cách mạng, năm 1969 thì ra Bắc. Năm 1973, bà lập gia đình mới. Năm 1980, bà về công tác tại Công ty Du lịch TP.HCM cho đến khi nghỉ hưu.[8]